% Version control information:
%\svnid{$Id: divide_venceras.tex 5 2009-03-29 23:59:23Z asalber $
%
\subsection{Divide y vencerás}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica de divide y vencerás}
\begin{itemize}
\item La técnica de \textbf{divide y vencerás} consiste básicamente en descomponer el problema inicial en varios subproblemas del mismo tipo pero más sencillos, resolver los subproblemas y combinar sus soluciones para obtener la solución del problema inicial.

\item El esquema que sigue es:
\begin{enumerate}
\item Dividir el problema en subproblemas del mismo tipo.
\item Resolver los subproblemas recursivamente.
\item Combinar las soluciones de los subproblemas para obtener la solución del problema original.
\end{enumerate}

\item A su vez, para resolver cada uno de los subproblemas puede volver a aplicarse la técnica de divide y vencerás recursivamente para descomponerlo en otros subproblemas de menor complejidad, y así hasta que los subproblemas obtenidos tengan una solución trivial.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo genérico de divide y vencerás}
\begin{lstlisting}
funcion divide_venceras(n)
  si n<n0
    s=resolver(n)
  si_no
    [n1,...,nk]=descomponer(n)
    desde i=1 hasta k hacer si=divide_venceras(ni)
    s=combinar(s1,...,sk)
  fin_si
  devolver s
fin_funcion
\end{lstlisting}
donde
\begin{itemize}
\item $n$ es el tamaño del problema,
\item $n_0$ es el umbral de tamaño por debajo del cual el problema se resuelve directamente (caso base de la recursión),
\item $n_i$ son los tamaños de los subproblemas en que se descompone el problema inicial,
\item $s_i$ son las soluciones de los subproblemas de tamaño $n_i$
\item $s$ es la solución del problema inicial.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Condiciones necesarias para aplicar divide y vencerás}
\begin{itemize}
\item Es necesario que el problema admita una formulación recursiva.
\item El problema inicial debe poder resolverse mediante la combinación de las soluciones de los subproblemas.
\item Los subproblemas deben ser del mismo tipo que el problema inicial pero con un tamaño estrictamente menor.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Condiciones deseables para aplicar divide y vencerás}
Además de las condiciones anteriores, si queremos que el algoritmo sea eficiente, debemos exigir las condiciones:
\begin{itemize}
\item El tamaño de los subproblemas debe ser lo más parecido posible y debe decrecer en progresión geométrica, es decir, debe ser $n/c$ con $c>1$.
\item Nunca se debe resolver un mismo subproblema más de una vez.
\item Las operaciones de descomponer y de combinar deben costar poco.
\item Hay que evitar generar nuevas llamadas cuando el tamaño de los subproblemas es suficientemente pequeño. Por tanto, hay que elegir bien el umbral $n_0$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal de un algoritmo con divide y vencerás}
Suponiendo que la función de descomposición origina $a$ subproblemas de tamaño $n/b$, el coste del algoritmo divide y vencerás es la suma de:
\begin{itemize}
\item El tiempo que tarda en descomponer el problema inicial: $t_d(n)$.
\item El tiempo que tarda en resolver los $k$ suproblemas en que se divide el problema original: $at(n/b)$.
\item El tiempo que tarda en combinar las soluciones de los subproblemas: $t_c(n)$
\end{itemize}
es decir
\[
t(n)=t_d(n)+at(n/b)+t_c(n).
\]
Si la descomposición y la combinación no son excesivamente costosas, tendrán a lo sumo un coste polinómico, es decir
\[
t(n) = at(n/b) + O(n^k),
\]
y como se trata de una recurrencia por cociente, su coste será:
\[
t(n)\in
\left\{%
\begin{array}{ll}
\Theta(n^k), & \hbox{si $a<b^k$;} \\
\Theta(n^k\log n), & \hbox{si $a=b^k$;} \\
\Theta(n^{\log_b a}), & \hbox{si $a>b^k$.} \\
\end{array}%
\right.
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de algoritmos con la técnica de divide y vencerás}
Algunos algoritmos conocidos que utilizan la técnica de divide y vencerás son:
\begin{itemize}
\item El algoritmo de búsqueda binaria.
\item El algoritmo de ordenación rápida Quicksort.
\item El algoritmo de cálculo de la mediana.
\item El algoritmo de Karatsuba y Ofman para la multiplicación de enteros grande.
\item El algoritmo de Strassen para el producto de matrices.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Búsqueda binaria}
\framesubtitle{Ejemplo de divide y vencerás}
La siguiente función en C++ reasliza una búsqueda binaria recursiva en un vector ordenado.
\begin{lstlisting}
// BusquedaBinaria.cpp
int busqueda_binaria(int x, const int a[], int i, int j){
  int k;
  if (i>j) return -1;
  else{
    k=(i+j)/2;
    if (a[k]==x) return k;
    else 
      if(a[k]>x) return busqueda_binaria(x,a,i,k-1);
      else return busqueda_binaria(x,a,k+1,j);
  }
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo de búsqueda binaria}
\framesubtitle{Ejemplo de divide y vencerás}
\begin{center}
\includegraphics[scale=0.45]{img/busqueda_binaria.eps} 
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal de la búsqueda binaria}
\framesubtitle{Ejemplo de divide y vencerás}
En la búsqueda binaria, el problema principal se descompone en 1 subproblema de tamaño $n/2$. Por otro lado, el coste de la descomposición y la combinación de soluciones es constante, así que el coste total es
\[t(n) = t(n/2) + O(1)‏.\]
Resolviendo la ecuación recursiva tenemos
\begin{align*}
t(n) &= t(n/2)+O(1) = t(n/4)+ 2 O(1) = \cdots \\
&= t(n/2^{\log_2 n})+\log_2 n O(1) = t(1) + \log_2 n O(1) =\\
&= 1 +\log_2 n O(1) \in O(\log n).
\end{align*}
Por tanto, \alert{\emph{¡el algoritmo de busqueda binaria es más eficiente que el de búsqueda lineal!}}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Multiplicación de enteros grandes}
\framesubtitle{Algoritmo clásico}
Todos conocemos el algoritmo para multiplicar enteros que nos enseñaron en el colegio
\[
\begin{array}{r}
\begin{array}{rrrrr}
* & * & * & * & * \\
* & * & * & * & * 
\end{array}
\\
n^2 \left\{
\begin{array}{rrrrrrrrr}
\hline
& & & & * & * & * & * & *\\
& & & * & * & * & * & * & \\
& & * & * & * & * & * & & \\
& * & * & * & * & * & & & \\
* & * & * & * & * & & & & \\
\hline
\end{array}
\right.
\\
\begin{array}{rrrrrrrrr}
* & * & * & * & * & * & * & * & *
\end{array}
\end{array}
\]
El coste de este algoritmo es $O(n^2)$.
\centerline{\emph{¿Se pueden multiplicar dos enteros con un coste menor?}}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Multiplicación de enteros grandes}
\framesubtitle{Ejemplo de divide y vencerás}
Supongamos que queremos multiplicar dos enteros $x$ e $y$ de tamaño $n$ expresados en una base $i$.
\[
\begin{array}{cp{2cm}}
n\mbox{ dígitos} & \\
\overbrace{
\begin{array}{cc}
\underbrace{
\begin{array}{|p{1cm}cp{1cm}|}
\hline
& a & \\
\hline\hline
& c & \\
\hline
\end{array}
}
&
\underbrace{\begin{array}{|p{1cm}cp{1cm}|}
\hline
& b & \\
\hline\hline
& d & \\
\hline
\end{array}
}
\\
n/2 & n/2
\end{array}
}
& \parbox{2cm}{$x = a\cdot i^{n/2} + b$\\ $y = c\cdot i^{n/2} + d$\\ \medskip\medskip }
\end{array}
\]
Se comprueba fácilmente que 
\[
xy = ac\cdot i^n + (ad+bc)\cdot i^{n/2} + bd
\]
y de esta forma, se puede calcular $xy$ mediante 4 productos entre enteros de tamaño $n/2$.

El coste que se obtiene es $t(n) = 4t(n/2) + O(n)$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal de la multiplicación de enteros grandes}
\framesubtitle{Ejemplo de divide y vencerás}
\begin{center}
\scalebox{0.44}{\LARGE
\pstree[nodesep=2pt]{\TR{\ $n$\ }}{ 
  \pstree {\TR{$n/2$}}{
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  } 
  \pstree{\TR{$n/2$}}{
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  }
  \pstree{\TR{$n/2$}}{
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  }
  \pstree{\TR{$n/2$}}{
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
       \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
	   \pstree{\TR{$n/4$}}{\pstree[linestyle=none,arrows=-,levelsep=1ex]{\Tfan[fansize=1cm]}{\TR{\vdots}}}
  }
}
}
\end{center}
\[
t(n) = \sum_{i=0}^{\log_2n} 4^i n/2^i =  n \sum_{i=0}^{\log_2n} 4^i/2^i = n \sum_{i=0}^{\log_2n} 2^i = n 2^{\log_2 n} = n^2 \in O(n^2).
\]
A pesar de utilizar la técnica de divide y vencerás, \alert{\emph{¡no es más eficiente que el anterior!}}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Multiplicación de enteros grandes de Karatsuba y Ofman}
\framesubtitle{Ejemplo de divide y vencerás}
Karatsuba y Ofman desarrollaron un algoritmo más eficiente a partir de la misma descomposición anterior pero basándose en la propiedad
\[
xy = ac\cdot i^n + ((a-b)(d-c)+ac+bd)\cdot i^{n/2} + bd
\]
De este modo, sólo se realizan $3$ productos de enteros de tamaño $n/2$.

El coste de este algorimo es 
\[
t(n) = 3t(n/2) + O(n) \in O(n^{1.57})‏.
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Multiplicación de enteros grandes de Karatsuba y Ofman}
\framesubtitle{Ejemplo de divide y vencerás}
Suponiendo que $x$ e $y$ son enteros de $n$ dígitos, el algoritmo de Karatsuba y Ofman puede escribirse así
\begin{lstlisting}[mathescape]
funcion productoK&O(enterogrande $x$, enterogrande $y$)
  si $n<=n_0$ devolver $xy$
  si_no
    $(a,b)$ = descomponer($x$)
    $(c,d)$ = descomponer($y$)
    $ac$ = productoK&O($a$,$c$)
    $bd$ = productoK&O($b$,$d$)
    $abdc$ = productoK&O($a-b$,$d-c$)
    devolver $ac*i^n + (abdc+ac+bd)*i^{n/2} + bd$
  fin_si
fin_funcion
\end{lstlisting}
Para que el algoritmo sea más eficiente debe fijarse el umbral en $n_0=500$ dígitos.
\end{frame}
